// 给定一个字符串s，一个字符串t
// 要求返回 s中涵盖t所有字符的最小子串，如果s中不存在涵盖t所有字符的子串，则返回空字符串''

// 思路：双指针，滑动窗口，需要对t字符串的字符做一个映射，然后遍历s，计算更新映射的值，当满足所有字符时，计算更新结果
// 然后继续更新left指针，重复寻求最小子串的解
// 时间复杂度：O(n)
// 空间复杂度：O(字符集的大小)

function minWindow(s, t) {
    const map = new Map()
    for (const item of t) {
        if (map.has(item)) {
            map.set(item, map.get(item) + 1)
        } else {
            map.set(item, 1)
        }
    }
    let left = 0
    let right = 0
    let result = ''
    let needType = map.size
    while (right < s.length) {
        if (map.has(s[right])) {
            map.set(s[right], map.get(s[right]) - 1)
        }
        if (map.get(s[right]) === 0) {
            needType--
        }
        while (needType === 0) {
            let str = s.substring(left, right + 1)
            if (!result || str.length < result.length) {
                result = str
            }
            if (map.has(s[left])) {
                map.set(s[left], map.get(s[left]) + 1)
                if (map.get(s[left]) === 1) {
                    needType++
                }
            }
            left++
        }
        right++
    }
    return result
}

let s = "ADOBECODEBANC", t = "ABC"

console.log(minWindow(s, t));